package 牛客.动态规划;

public class 力扣1143最长公共子序列 {
    //注意 718最长重复数组的长度，要求元素是连续的；但本题要求字符可以不连续，但是要求字符相同，相对顺序也相同
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp=new int[text1.length()+1][text2.length()+1];
        //dp[i][j] 代表  字符串s1从[0,i-1]的字符中 和 字符串2从[0,j-1]的字符中，它两最长公共子序列的最大长度
        for (int i = 1; i <text1.length()+1 ; i++) {
            for (int j = 1; j <text2.length()+1 ; j++) {
                if (text1.charAt(i-1)==text2.charAt(j-1)) {
                    dp[i][j]=dp[i-1][j-1]+1;//递归公式，当前这两字符一样，那么就要找到它两对应前一个字符的公共子序列的最大长度
                }else {
                    //和718不同之处：对于不相等的两个字符也要进行处理，保存当前公共子序列最大长度的数值
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}
